#include<unordered_map>
#include<list>
class FreqStack {
public:
    int maxF = 0;
    std::unordered_map<int, int> freqMap;
    std::unordered_map<int,std::list<int>> freqList;
    FreqStack() {
        
    }

    int findMap(int val)
    {
        if (freqMap.find(val) == freqMap.end())
        {
            //没找到
            freqMap.insert({val,1});
            return 1;
        }
        else
        {
            //找到了
            return(++freqMap[val]);
        }
    }

    void push(int val)
    {
        int frKey = findMap(val);
        if (freqList.find(frKey) == freqList.end())
        {
            //没找到
            freqList.insert({frKey,{val}});
            maxF=frKey;
        }
        else
        {
           //找到了
            freqList[frKey].push_back(val);
        }
    }

    int pop() {
        int value = freqList[maxF].back();
        freqList[maxF].pop_back();
        if (freqList[maxF].empty())
        {
            //empty
            freqList.erase(maxF);
            maxF-=1;
            
        }else
        {
            //notempty
        }
        freqMap[value]--;
        if (freqMap[value] == 0)
        {
            freqMap.erase(value);
        }
        return value;
    }
};
